// arr n emements find target
template<typename T>
long long binarySearch(T arr[], long long n, T target){
	// [l, r] 区间寻找target
	long long l = 0, r = n - 1;
	// l == r时,区间[l...r]依然是有效的,只有一个元素
	while(l <= r){
		long long mid = l + (r - l) / 2;
		if(arr[mid] == target) return mid;
		
		if(target > arr[mid])
			l = mid + 1;
		else
			r = mid - 1;
	}
	
	return -1;
}


